package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @Class sword_offer.Code37
 * @Description 请实现 copyRandomList 函数，复制一个复杂链表。
 * 在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 * 示例 1：
 * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 *
 * 示例 2：
 * 输入：head = [[1,1],[2,1]]
 * 输出：[[1,1],[2,1]]
 *
 * 示例 3：
 * 输入：head = [[3,null],[3,0],[3,null]]
 * 输出：[[3,null],[3,0],[3,null]]
 *
 * 示例 4：
 * 输入：head = []
 * 输出：[]
 * 解释：给定的链表为空（空指针），因此返回 null。
 *
 *
 * 提示：
 * -10000 <= Node.val <= 10000
 * Node.random为空（null）或指向链表中的节点。
 * 节点数目不超过 1000 。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-20 10:48
 */
public class Code37 {

    public static void main(String[] args) {
        Node n1 = new Node(7);
        Node n2 = new Node(13);
        Node n3 = new Node(11);
        Node n4 = new Node(10);
        Node n5 = new Node(1);

        n1.random = null;
        n1.next = n2;

        n2.random = n1;
        n2.next = n3;

        n3.random = n5;
        n3.next = n4;

        n4.random = n3;
        n4.next = n5;

        n5.random = n1;
        n5.next = null;

        Node node = copyRandomList(n1);
    }

    public static Node copyRandomList(Node head) { // 传入的head是原链表的head
        if (head == null) {
            return null; // head为空返回null
        }

        // 1. 第一步完成链表的复制操作
        Node cur = head; // 这个变量用来作为链表的指针
        while (cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }

        // 2. 第二步完成random指针的赋值
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next; // 如果当前结点的random指针为空的话不用赋值，默认就是空
            }
            cur = cur.next.next;
        }

        // 3. 完成对链表的拆分
        cur = head;
        Node newHead = head.next;
        while (cur.next != null) {
            Node temp = cur.next;
            cur.next = temp.next;
            cur = temp;
        }
        return newHead;
    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
/*
首先递归的方法是不能解决问题的
递归只能返回填充好next指针的链表
但是没办法求出random指针
最好的做法是遍历原链表
将每一个结点的复制品连接到该节点后形成一条double的新旧间隔的链表
然后对链表进行random的复制
最后对链表进行拆分
 */